import numpy as np
import matplotlib.pyplot as plt


class Routeplan:
    def __init__(self):
        citys = [[18.4700, 95.1000],
                 [16.4700, 94.6400],
                 [20.0900, 94.5400],
                 [14.3900, 93.3700],
                 [25.2300, 97.2400],
                 [22.0000, 93.0500],
                 [23.4700, 92.0200],
                 [16.2000, 96.2900],
                 [17.3000, 97.3800],
                 [13.0500, 98.1200],
                 [15.5300, 97.3800],
                 [24.5200, 95.5900],
                 [16.4100, 97.1300],
                 [15.0900, 92.5500]]
        self.citys = citys

#  计算点和点之间的距离，并形成矩阵
    @staticmethod
    def distance_compute(city):
        n = len(city)
        d = np.zeros((n, n))
        for i in range(0, n):
            d[i][i] = 0.0001
            for k in range(0, n):
                j = i + k
                if j < n:
                    d[i][j] = np.sqrt(
                        (city[i][0] - city[j][0]) * (city[i][0] - city[j][0]) + (city[i][1] - city[j][1]) * (
                                    city[i][1] - city[j][1]))
                    d[j][i] = d[i][j]
                else:
                    break
        return d

#  查找合乎条件的列表索引值
    @staticmethod
    def lookfor_index(a, func):
        return [i for (i, val) in enumerate(a) if func(val)]

    #  算法主函数 包括初始化运行参数
    def main(self):
        n = len(self.citys)
        d = self.distance_compute(city=self.citys)
        nc_max = 200        # 迭代次数
        m = 22              # 蚂蚁个数
        alpha = 1           # α 选择[1, 4]比较合适
        beta = 4            # β 选择[3 4 5]比较合适
        rho = 0.2           # ρ 选择[0.1, 0.2, 0.5]比较合适
        q = 20
        nc = 1              # 迭代次数，一般从1开始
        eta = 1 / d         # 表示矩阵 取倒数
        tau = np.ones((n, n))                    # 边（i, j）的信息素，一般开始为1
        route_table = np.zeros((m, n))           # 路径记录表
        rbest = np.zeros((nc_max, n))            # 记录各代最佳路线
        lbest = np.inf * np.ones((nc_max, 1))    # 记录各代的最佳路线总长度
        laverage = np.zeros((nc_max, 1))         # 各代路线的平均长度
        # 迭代寻找最佳路径
        while nc <= nc_max:
            # 第一步：随机产生各个蚂蚁的起点城市
            start = np.zeros((m, 1))
            for i in range(0, m):
                temp = np.random.permutation(n)                  # 随机排列一个长度为n,数值 <= n的序列
                start[i] = temp[0]                               # 可能为0
            route_table[:, [0]] = start                          # 路径记录表的第一列为所有蚂蚁的起点城市
            citys_index = list(range(0, n))
            # 第二步：逐个蚂蚁路径选择
            for i in range(0, m):                                # 逐个城市路径选择
                for j in range(1, n):
                    tabu = route_table[i][0:(j - 1)]             # 蚂蚁i已经访问过的城市——禁忌表
                    allow_index = np.array(~np.in1d(citys_index, tabu))  # 检查禁忌表是否在索引城市中，访问过则为0，未访问过则为1，返回一个列表。(~为取反操作)
                    allow_index = allow_index.astype(int)
                    allow = []
                    for t in range(0, len(allow_index)):
                        if allow_index[t] == 1:
                            allow_citys = allow.append(citys_index[t])
                        else:
                            pass
                    # allow = np.array(citys_index)[allow_index]   # allow表，存放待访问城市，allow_index中为1的继续保留，为0的抛弃。
                    p = allow
                    # 计算从城市j到剩下未访问的城市的转移概率
                    for k in range(0, len(allow)):           # 待访问的城市数量
                        p[k] = (tau[len(tabu)-1][allow[k]] ** alpha) * (eta[len(tabu)-1][allow[k]] ** beta)
                    p = p / sum(p)                               # 归一化
                    # 轮盘赌法选择下一个访问城市(增加随机性)
                    pc = np.cumsum(p)                            # 矩阵的行累积和
                    target_index = list(self.lookfor_index(pc, lambda x: x >= np.random.rand()))
                    target = allow[target_index[0]]
                    route_table[i][j] = target
            # 第三步：计算各个蚂蚁的路径距离
            length = np.zeros((m, 1))
            for i in range(0, m):
                route = route_table[i, :]
                for j in range(0, (n-1)):
                    ant_distance = [route[j], route[j+1]]
                    length[i] = length[i] + self.distance_compute(city=ant_distance)
                ant_distance_i = [route[n], route[1]]
                length[i] = length[i] + self.distance_compute(city=ant_distance_i)
            # 第四步：计算最短路径距离及平均距离
            if nc == 1:
                [min_length, min_index] = min(length)
                lbest[nc] = min_length
                laverage[nc] = np.mean(length)
                rbest[nc, :] = route_table[min_index, :]
            else:
                [min_length, min_index] = min(length)
                lbest[nc] = min(lbest(nc - 1), min_length)
                laverage[nc] = np.mean[length]
                if lbest[nc] == min_length:
                    rbest[nc, :] = route_table[min_index, :]
                else:
                    rbest[nc, :] = rbest[(nc - 1), :]
            # 第五步：更新信息素
            delta_tau = np.zeros((n, n))
            for i in range(0, m):
                for j in range(0, (n-1)):
                    delta_tau[route_table[i, j]][route_table[i, j+1]] = delta_tau[route_table[i, j]][route_table[i, j+1]] + q / length[i]
                delta_tau[route_table[i, n]][route_table[i, 1]] = delta_tau[route_table[i, n]][route_table[i, 1]] + q / length[i]
            tau = (1 - rho) * tau + delta_tau
            # 第六步：迭代次数加1，并且清空路径记录表
            nc = nc + 1
            route_table = np.zeros((m, n))
        # 显示规划结果
        [shortest_length, shortest_index] = min(lbest)
        shortest_route = rbest[shortest_index, :]
        print('最短距离：' + str(shortest_length))
        print('最短路径：' + str([shortest_route, shortest_route[1]]))
        # 绘制图形
        plt.figure(num=1)
        plt.plot([self.citys[shortest_route][0], self.citys[shortest_route[0]][0]], [self.citys[shortest_route][1], self.citys[shortest_route[0]][1]], color='b', linecache='o-')
        plt.grid('on')
        for i in range(0, len(self.citys)):
            plt.annotate('点i', (self.citys[i][0], self.citys[i][1]), xytext=(self.citys[i][0]+1, self.citys[i][1]+1))
        plt.annotate('起点', (self.citys[shortest_route[0]][0], self.citys[shortest_route[0]][1]), xytext=(self.citys[shortest_route[0]][0]+1, self.citys[shortest_route[0]][1]+1))
        plt.annotate('终点', (self.citys[shortest_route[-1]][0], self.citys[shortest_route[-1]][1]),
                     xytext=(self.citys[shortest_route[-1]][0] + 1, self.citys[shortest_route[-1]][1] + 1))
        plt.xlabel('城市位置横坐标')
        plt.ylabel('城市位置纵坐标')
        plt.title('蚁群算法优化路径（最短距离为：' + str(shortest_length) + '）')
        plt.figure(num=2)
        plt.plot(range(0, nc_max), lbest, 'b', range(0, nc_max), laverage, 'r')
        plt.legend('最短距离', '平均距离')
        plt.xlabel('迭代次数')
        plt.ylabel('距离')
        plt.title('各代最短距离与平均距离对比')


ant_routeplan = Routeplan()
ant_routeplan.main()




















